package project.euler.honk.problem.to50;

public final class Problem15 {

	private static final int SIZE = 21;
	private static final long[][] data;

	static {
		data = new long[SIZE][];
		for (int i = 0; i < SIZE; i++) {
			data[i] = new long[SIZE];
		}
		for (int i = 0; i < SIZE; i++) {
			data[SIZE - 1][i] = 1;
			data[i][SIZE - 1] = 1;
		}
	}

	private static void builtUp() {
		for (int i = SIZE - 2; i >= 0; i--) {
			for (int j = i; j >= 0; j--) {
				data[i][j] = data[i][j + 1] + data[i + 1][j];
				data[j][i] = data[j][i + 1] + data[j + 1][i];
			}
		}
	}

	public static long solve() {
		builtUp();
		return data[0][0];
	}

	public static void main(String[] args) {
		long start = System.currentTimeMillis();
		long result = solve();
		long end = System.currentTimeMillis();
		System.out.println("Result: " + result + " Time: " + (end - start));
	}
}
